package com.bjsxt.datastructure.sort;

import java.util.Arrays;

public class TestQuickSort {
    public static void main(String[] args) {
        //定义一个无序数组
        int[] arr = {8, 9, 4, 5, 6, 1, 0};
        //输出无序数组
        System.out.println(Arrays.toString(arr));
        //对无序数组快速排序
        quickSort(arr);
        //输出有序数组
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr, low, high);
    }

    private static void quickSort(int[] arr, int low, int high) {
       if (low < high) {
           //找到分区数据的索引
           int index = getPartition(arr, low, high);
           //对左侧进行排序
           quickSort(arr, low, index - 1);
           //对右侧进行排序
           quickSort(arr, index + 1, high);
       }
    }

    private static int getPartition(int[] arr, int low, int high) {
        //指定左指针i和右指针j
        int i = low;
        int j = high;

        //找到基准值
        int x = arr[i];

        //使用循环，实现分区
        while (i < j) {
            //从右向左移动j,找到第一个小于基准值的值（这个值将成为下一个坑）
            while (arr[j] >= x && i < j) {
                j--;
            }
            //将这个值放到坑中，左侧指针向右移动一位，i++
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            //从左向右移动i，找到第一个大于基准值的值（这个值将成为下一个坑）
            while (arr[i] < x && i < j) {
                i++;
            }
            // 将这个值放入坑中，右侧指针向左移动一位，j--
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }

        //使用基准值填坑，这就是基准值的最终位置
        arr[i] = x;
        //返回基准值填坑位置的索引
        return i;
    }
}
